#include "huffmantree.cpp"
#include <vector>

#define NEW_NODE (HuffmanNode *)malloc(sizeof(HuffmanNode))

using namespace std;

typedef struct HuffmanCode
{
	char ch;
	int weight;
}HuffmanCode;

HuffmanTree BuildHuffmanTree(vector<HuffmanCode> HuffmanSpace);

int main(void)
{
	vector<HuffmanCode> HuffmanSpace;
	char tc;
	int tn;
	HuffmanCode temp;
	HuffmanTree FinalTree;
	do
	{
		cin >> tc >> tn;
		if(tc == '#')
			break;
		else
		{
			temp.ch = tc;
			temp.weight = tn;
			HuffmanSpace.push_back(temp);
		}
	}while(1);
	FinalTree = BuildHuffmanTree(HuffmanSpace);
	cout << "The weighed length of the Huffman tree is: " << FinalTree.WeighedLength() << endl;
	cout << "The HuffmanCode" << endl << "letter\tcode" << endl;
	FinalTree.Output();
	return 0;
}

HuffmanTree BuildHuffmanTree(vector<HuffmanCode> HuffmanSpace)
{
	vector<HuffmanTree> forest;
	vector<HuffmanTree>::iterator t;
	HuffmanTree mina, minb;
	vector<HuffmanCode>::iterator cpointer;
	for(cpointer = HuffmanSpace.begin(); cpointer != HuffmanSpace.end(); cpointer++)
	{
		HuffmanTree teTree(cpointer->ch, cpointer->weight);
		for(t = forest.begin(); t != forest.end() && (t->root->weight < cpointer->weight); t++);
		forest.insert(t, teTree);
	}
	while(forest.size() > 1)
	{
		mina = forest[0];
		minb = forest[1];
		forest.erase(forest.begin(), forest.begin()+2);
		HuffmanTree temp(mina, minb);
		for(t = forest.begin(); t != forest.end() && (t->root->weight < temp.Weight()); t++);
		forest.insert(t, temp);
	}
	return forest[0];
}

